% Created 2020-01-07 二 16:36
% Intended LaTeX compiler: pdflatex
\documentclass[11pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{graphicx}
\usepackage{grffile}
\usepackage{longtable}
\usepackage{wrapfig}
\usepackage{rotating}
\usepackage[normalem]{ulem}
\usepackage{amsmath}
\usepackage{textcomp}
\usepackage{amssymb}
\usepackage{capt-of}
\usepackage{hyperref}
\usepackage{minted}
\input{preamble.tex}
\author{Robert I. Soare}
\date{\today}
\title{Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets}
\hypersetup{
 pdfauthor={Robert I. Soare},
 pdftitle={Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets},
 pdfkeywords={},
 pdfsubject={},
 pdfcreator={Emacs 26.3 (Org mode 9.3)}, 
 pdflang={English}}
\begin{document}

\maketitle
\tableofcontents \clearpage
\section{Recursive Functions}
\label{sec:org0ffea22}
\subsection{Formal Definitions of Computable Functions}
\label{sec:orgc1a3b08}
\subsubsection{Primitive Recursive Functions}
\label{sec:org5192850}
\begin{definition}[]
The class of primitive recursive functions is the smallest class \(\calc\) of
functions closed under the following schema
\begin{enumerate}
\item the \tf{successor function}, \(\lambda x[x+1]\in\calc\)
\item the \tf{constant functions}, \(\lambda x_1\dots x_n[m]\in\calc\), \(0\le n,m\)
\item the \tf{identity functions}, \(\lambda x_1\dots x_n[x_i]\in\calc\), \(1\le
      i\le n\)
\item (Composition) If \(g_1,\dots,g_m,h\in\calc\), then
\begin{equation*}
f(x_1,\dots,x_n)=h(g_1(x_1,\dots,x_n),\dots,g_m(x_1,\dots,x_n))
\end{equation*}
is in \(\calc\) where \(g_1,\dots,g_m\) are functions of \(n\) variables and \(h\)
is a function of \(m\) variables
\item (Primitive Recursion) If \(g,h\in\calc\) and \(n\ge 1\) then \(f\in\calc\) where
\begin{gather*}
f(0,x_2,\dots,x_n)=g(x_2,\dots,x_n)\\
f(x_1+1,x_2,\dots,x_n)=h(x_1,f(x_1,\dots,x_n),x_2,\dots,x_n)\\
\end{gather*}
\end{enumerate}
\end{definition}


Hence a function is primitve recursive if there is a \tf{derivation}, namely
a sequence \(f_1,\dots,f_k=f\) s.t. for each \(f_i,i\le k\) is either an initial
function or obtained from 4 or 5.

A predicate (relation) is \tf{primitive recursive} if its characteristic
function is.
\subsubsection{Diagonalization and Partial Recursive Functions}
\label{sec:org8515379}
Although the primitive recursive functions include all the usual functions
from elementary number theory they fail to include \tf{all} computable
functions. Each derivation of a primitive recursive function is a finite
string of symbols from a fixed finite alphabet, and thus all derivations can
be effectively listed. Let \(f_n\) be the function corresponding to the \(n\)th
derivation in this listing. Then the function \(g(x)=f_x(x)+1\) cannot be
primitive recursive.

The same argument applies to any effective set of schemata which produces
only \tf{total} functions. Thus to obtain all computable functions we are
forced to consider computable \tf{partial} functions.

\begin{definition}[Kleene]
The class of \tf{partial recursive} (p.r.) functions is the least class
obtained by closing under schemata 1 through 5 for the primitive recursive
functions and the following schemata 6. A \tf{total recursive} function
(abbreviated \tf{recursive} function) is a partial recursive function which
is total.
\begin{enumerate}
\setcounter{enumi}{5}
\item (Unbounded Search) If \(\theta(x_1,\dots,x_n,y)\) is a partial
recursive function of \(n+1\) variables, and 
\begin{align*}
\psi(x_1,\dots,x_n)=\mu y[\theta&(x_1,\dots,x_n,y)\downarrow=0\\
&\wedge (\forall z\le y)[\theta(x_1,\dots,x_n,z)\downarrow]]
\end{align*}
\end{enumerate}
\end{definition}
\begin{definition}[]
A relation \(R\subseteq \omega^n,n\ge 1\) is \tf{recursive} (\tf\{primitive
recursive, has property \} \(P\)) if its characteristic function \(\chi_R\) is
recursive (primitive recursive) where \(\chi_R(x_1\dots,x_n)=1\) if and only if
\((x_1,\dots,x_n)\in R\).
\end{definition}
\subsubsection{Turing Computable Functions}
\label{sec:org4550c29}
A \tf{Turing machine} \(M\) includes a two-way infinite \tf{tape} divided into
\tf{cells}, a \tf{reading head} which scans one cell of the tape at a time,
and a finite set of internal \tf{states} \(Q=\{q_0,\dots,q_n\},n\ge 1\). Each
cell is either blank (B) or has written on it the symbol 1. In a single step
the machine may simultaneously
\begin{enumerate}
\item change from one state to another
\item change the scanned symbol \(s\) to another symbol \(s'\in S=\{1,B\}\)
\item move the reading head one cell to the right (R) or left (L)
\end{enumerate}


The operation of \(M\) is controlled by a partial map 
\(\delta:Q\times S\to Q\times S\times\{R,L\}\)

The map \(\delta\) viewed as a finite set of quintuples is called a \tf\{Turing
program\}. The \tf{input} integer \(x\) is represented by a string of \(x+1\)
consecutive 1's.
\subsection{The Basic Results}
\label{sec:org4da9d58}
\textbf{Church's Thesis} asserts that these functions coincide with the
intuitively computable functions. We shall accept Church's Thesis and from
now on shall use the terms "partial recursive" "Turing computable" and
"computable" interchangeably

\begin{definition}[]
Let \(P_e\) be the Turing program with code number (Gödel number) \(e\) 
(also called \textbf{index} \(e\)) in this
listing and let \(\varphi_e^{(n)}\) be the partial fucntions of \(n\) variables
computed by \(P_e\), where \(\varphi_e\) abbreviates \(\varphi_e^{(1)}\)
\end{definition}

\begin{lemma}[Padding Lemma]
Each partial recursive function \(\varphi_x\) has \(\aleph_0\) indices, and
furthermore for each \(x\) we can effectively find an infinite set \(A_x\) of
indices for the same partial function
\end{lemma}


\begin{proof}
For any program \(P_x\) mentioning internal states \(\{q_0,\dots,q_n\}\) add
extraneous instructions \(q_{n+1}Bq_{n+1}BR,q_{n+2}Bq_{n+2},BR,\dots\) to get
new programs for the same functions
\end{proof}
\begin{theorem}[Normal Form Theorem (Kleene]
There exist a predicate \(T(e,x,y)\) (called the \textbf{Kleene T-predicate}) and a
function \(U(y)\) which are recursive (indeed primitive recursive) s.t.
\begin{equation*}
\varphi_e(x)=U(\mu y T(e,x,y))
\end{equation*}
\end{theorem}

It follows from the Normal Form Theorem that every Turing computable partial
function is partial recursive.

\begin{theorem}[Enumeration Theorem]
There is a p.r. function of 2 variables \(\varphi_z^{(2)}(e,x)\) s.t.
\(\varphi_z^{(2)}(e,x)=\varphi_e(x)\). Indeed the Enumeration Theorem holds for
p.r. functions of \(n\) variables
\end{theorem}
\begin{proof}
Let \(\varphi_z^{(2)}(e,x)=U(\mu y T(e,x,y))\). For
\(\varphi_z^{(n)}(e,x_1,\dots,x_{n-1})\), by \(s\)-\(m\)-\(n\) theorem, 
\begin{equation*}
\varphi_z^{(n)}(e,\bar{x})=
\varphi_{s^2_{n-1}(z,e)}^{(n-1)}(\bar{x})
\end{equation*}
Thus we only need to make sure that \(s^2_{n-1}(z,e)\in A_e\), which can be
effectively found.
\end{proof}
\begin{theorem}[Parameter Theorem ($s$-$m$-$n$ Theorem)]
For every \(m,n\ge 1\) there exists a 1:1 recursive function \(s^m_n\) of \(m+1\)
variables s.t. for all \(x,y_1,y_2,\dots,y_m\)
\begin{equation*}
\varphi_{s^m_n(x,y_1,\dots,y_m)}^{(n)}=\lambda z_1,\dots,z_n
(\varphi_x^{(m+n)}(y_1,\dots,y_m,z_1,\dots,z_n))
\end{equation*}
\end{theorem}
\begin{proof}
\emph{(informal)}. For simplicity consider the case \(m=n=1\). The program
\(P_{s_1^1(x,y)}\) on input \(z\) first obtains \(P_x\) and then applies \(P_x\) to
input \((y,z)\)
\end{proof}

\begin{remark}
Here is an interesting question in \href{https://cs.stackexchange.com/questions/80837/is-smn-theorem-the-same-concept-as-currying}{StackExchange}
\end{remark}

The \(s\)-\(m\)-\(n\) theorem asserts that \(y\) may be treated as a fixed parameter
in the program \(P_{s(x,y)}\) which operate on \(z\) and furthermore that the
index \(s(x,y)\) of this program is effective in \(x\) and \(y\). A simple
application of the \$s\$-\$m\$-\(n\) theorem is the existence of a recursive
function \(f(x)\) s.t. \(\varphi_{f(x)}=2\varphi_x\). Let
\(\psi(x,y)=2\varphi_x(y)\). By Church's Thesis
\(\psi(x,y)=\varphi_e^{(2)}(x,y)\) for some \(e\). Let \(f(x)=s^1_1(e,x)\)

We let \(\la x,y\ra\) denote the image of \((x,y)\) under the standard pairing
function \(\frac{1}{2}(x^2+2xy+y^2+3x+y)\) which is a bijective recursive
function from \(\omega^2\to\omega\). Let \(\pi_1\) and \(\pi_2\) denote the inverse
functions \(\pi_1(\la x,y\ra)=x\)

\begin{definition}[]
We write \(\varphi_{e,s}(x)=y\) if \(x,y,e<s\) and \(y\) is the output
\(\varphi_e(x)\) in \(<s\) steps of the Turing machine \(P_e\). If such a \(s\)
exists we say \(\varphi_{e,s}(x)\) \tf{converges}, which we write as 
\(\varphi_{e,s}(x)\downarrow\), and \tf{diverges} (\(\varphi_{e,s}(x)\uparrow\)).
Similarly, we write \(\varphi_e(x)\downarrow\) if \(\varphi_{e,s}(x)\downarrow\)
for some \(s\)
\end{definition}

\begin{theorem}[]
\begin{enumerate}
\item The set \(\{\la e,x,s\ra:\varphi_{e,s}(x)\downarrow\}\) is recursive
\item The set \(\{\la e,x,y,s\ra:\varphi_{e,s}(x)=y\}\) is recursive
\end{enumerate}
\end{theorem}
\begin{proof}
From Church's Thesis since they are all computable
\end{proof}
\subsection{Recursively Enumerable Sets and Unsolvable Problems}
\label{sec:orge38b491}
\begin{definition}[]
\begin{enumerate}
\item A set \(A\) is \textbf{recursively enumerable} (r.e.) if \(A\) is the domain of
some p.r. function
\item let the \(e\)th r.e. set be denoted by
\begin{equation*}
W_e=\dom{\varphi_e}=\{x:\varphi_e(x)\downarrow\}=\{x:(\exists y)T(e,x,y)\}
\end{equation*}
\item \(W_{e,s}=\dom{\varphi_{e,s}}\)
\end{enumerate}
\end{definition}

Note that \(\varphi_e(x)=x\) iff \((\exists s)[\varphi_{e,s}=y]\) and 
\(x\in W_e\) iff \((\exists s)(x\in W_{e,s})\)

\begin{definition}[]
Let \(K=\{x:\varphi_x(x)\text{ converges }\}=\{x:x\in W_x\}\)
\end{definition}
\begin{proposition}[]
\(K\) is r.e.
\end{proposition}
\begin{proof}
\(K\) is the domain of the following p.r. function
\begin{equation*}
\psi(x)=
\begin{cases}
x&\text{if } \varphi_x(x)\text{ converges},\\
\text{undefined}&\text{otherwise}
\end{cases}
\end{equation*}
Now \(\psi\) is p.r. by Church's Thesis since \(\psi(x)\) can be computed by
applying program \(P_x\) to input \(x\) and giving output \(x\) only if
\(\varphi(x)\) converges. Alternatively and more formally,
\(K=\dom{\theta}\) where \(\theta(x)=\varphi_z^{(2)}(x,x)\) for \(\varphi_z^{(2)}\)
the p.r. function defined in the Enumeration Theorem
\end{proof}
\begin{corollary}[]
\label{col1}
\(K\) is not recursive
\end{corollary}
\begin{proof}
If \(K\) had a recursive characteristic function \(\chi_K\) then the following
function would be recursive
\begin{equation*}
f(x)=
\begin{cases}
\varphi_x(x)+1&\text{if }x\in K\\
0&\text{if }x\not\in K
\end{cases}
\end{equation*}
However \(f\) cannot be recursive since \(f\neq\varphi_x\) for any \(x\)
\end{proof}
\begin{definition}[]
\(K_0=\{\la x,y\ra:x\in W_y\}\)
\end{definition}
\(K_0\) is p.r. but

\begin{proposition}[]
\(K_0\) is not recursive
\end{proposition}
\begin{proof}
\(x\in K\) iff \(\la x,x\ra\in K\)
\end{proof}

The \tf{halting problem} is to decide for arbitrary \(x\) and \(y\) whether
\(\varphi_x(y)\downarrow\). Corollary \ref{col1} asserts the unsolvability of the
halting problem.

\begin{definition}[]
\begin{enumerate}
\item \(A\) is a \tf{many-one reducible} (\tf{m-reducible}) to \(B\) (written
\(A\le_m B\)) if there is a recursive function \(f\) s.t. \(f(A)\subset B\) and
\(f(\bar{A})\subseteq\bar{B}\), i.e. \(x\in A\) iff \(f(x)\in B\)
\item \(A\) is \tf{one-one reducible} (\tf{1-reducible}) to \(B\) (\(A\le_1 B\)) if
\(A\le_m B\) by a 1:1 recursive function
\end{enumerate}
\end{definition}

The proof of corollary \ref{col1} established that \(K\le_1 K_0\) via the
function \(f(x)=\la x,x\ra\)
\begin{definition}[]
\begin{enumerate}
\item \(A\equiv_m B\) if \(A\le_m B\) and \(B\le_m A\)
\item \(A\equiv_1 B\) if \(A\le_1 B\) and \(B\le_1 A\)
\item \(\deg_m(A)=\{B:A\equiv_m B\}\)
\item \(\deg_1(A)=\{B:A\equiv_1 B\}\)
\end{enumerate}
\end{definition}

The equivalence classes under \(\equiv_m\) and \(\equiv_1\) are called the
\textbf{m-degrees} and \textbf{1-degrees} respectively

\begin{proposition}[]
If \(A\le_m B\) and \(B\) is recursive then \(A\) is recursive
\end{proposition}

\begin{proof}
\(\chi_A(x)=\chi_B(f(x))\)
\end{proof}

\begin{theorem}[]
\label{thm1}
\(K\le_1\text{Tot}:=\{x:\varphi_x\text{ is a total function}\}\)
\end{theorem}
\begin{proof}
Define the function
\begin{equation*}
\psi(x,y)=
\begin{cases}
1&\text{if } x\in K\\
\text{undefined} &\text{otherwise}
\end{cases}
\end{equation*}
By \(s\)-\(m\)-\(n\) theorem, there is a 1:1 recursive function \(f\) s.t.
\(\varphi_{f(x)}(y)=\psi(x,y)\). Choose \(e\) s.t. \(\varphi_e(x,y)=\psi(x,y)\) 
since \(\psi\) is p.r. and
define \(f(x)=s_1^1(e,x)\). Note that
\begin{align*}
&x\in K\Longrightarrow \varphi_{f(x)}=\lambda y[1]\Longrightarrow\varphi_{f(x)}\text{ total}
\Longrightarrow f(x)\in\text{Tot}\\
&x\not\in K\Longrightarrow\varphi_{f(x)}=\lambda y[\text{undefined}]\Longrightarrow
\varphi_{f(x)}\text{ not total}\Longrightarrow f(x)\not\in\text{Tot}
\end{align*}
\end{proof}

\begin{definition}[]
A set \(A\subseteq\omega\) is an \tf{index set} if for all \(x\) and \(y\)
\begin{equation*}
(x\in A\wedge\varphi_x=\varphi_y)\Longrightarrow y\in  A
\end{equation*}
\end{definition}

\begin{theorem}[]
If \(A\) is a nontrivial index set, i.e., \(A\neq \emptyset,\omega\), then either
\(K\le_1 A\) or \(K\le_1\overline{A}\)
\end{theorem}

\begin{proof}
Choose \(e_0\) s.t. \(\varphi_{e_0}(y)\) is undefined for all \(y\). If
\(e_0\in\overline{A}\), then \(K\le_1 A\) as follows. Since \(A\neq\emptyset\) we can
choose \(e_1\in A\). Now \(\varphi_{e_1}\neq\varphi_{e_0}\) because \(A\) is an
index set. By \(s\)-\(m\)-\(n\) theorem define a 1:1 recursive function \(f\)
s.t.
\begin{equation*}
\varphi_{f(x)}(y)=
\begin{cases}
\varphi_{e_1}(y)&x\in K\\
\text{undefined}&x\not\in K
\end{cases}
\end{equation*}
Now
\begin{align*}
&x\in K\Longrightarrow\varphi_{f(x)}=\varphi_{e_1}\Longrightarrow f(x)\in A\\
&x\not\in K\Longrightarrow\varphi_{f(x)}=\varphi_{e_0}\Longrightarrow
f(x)\in\overline{A}
\end{align*}
\end{proof}

It's possible that both \(K\le_1 A\) and \(K\le_1\overline{A}\) for an index set
\(A\), for example if \(A=\text{Tot}\)
\begin{corollary}[Rice's Theorem]
Let \(\calc\) be any class of partial recursive functions. Then
\(\{n:\varphi_n\in\calc\}\) is recursive iff \(\calc=\emptyset\) or \(\calc\) is
the set of all partial recursive functions
\end{corollary}
\begin{proof}
\(\calc\) is an index set and hence is trivial.
\end{proof}
\begin{definition}[]
\begin{align*}
&K_1=\{x:W_x\neq\emptyset\}\\
&\text{Fin}=\{x:W_x\text{ is finite}\}\\
&\text{Inf}=\omega-\text{Fin}=\{x:W_x\text{ is infinite}\}\\
&\text{Tot}=\{x:\varphi_x\text{ is total}\}=\{x:W_x=\omega\}\\
&\text{Con}=\{x:\varphi_x\text{ is total and constant}\}\\
&\text{Cof}=\{x:W_x\text{ is cofinite}\}\\
&\text{Rec}=\{x:W_x\text{ is recursive}\}\\
&\text{Ext}=\{x:\varphi_x\text{ is extendible to a total recursive function}\}\\
\end{align*}
\end{definition}
\begin{definition}[]
An r.e. set \(A\) is \textbf{1-complete} if \(W_e\le_1 A\) for every r.e. set \(W_e\)
\end{definition}

\(K_0\) is 1-complete because \(x\in W_e\) iff \(\la x,e\ra\in K_0\)

\begin{definition}[]
Let \(A\) \textbf{join} \(B\) written \(A\oplus B\) be
\begin{equation*}
\{2x:x\in A\}\cup\{2x+1:x\in B\}
\end{equation*}
\end{definition}
\begin{exercise}
\begin{enumerate}
\item \(A\le_m A\oplus B\) and \(B\le_M A\oplus B\)
\item if \(A\le_m C\) and \(B\le_m C\) then \(A\oplus B\le_m C\)
\end{enumerate}
\end{exercise}

\begin{exercise}
\(K\equiv_1 K_0\equiv_1 K_1\)
\end{exercise}
\begin{proof}
From proof of theorem \ref{thm1}, \(K\le_1 A\) for \(A=K_1,\text{con}\) or
\(\text{Inf}\).

\(K_0\le K\) for the same reason.

This method only concerns with the latter item.
\end{proof}

\begin{exercise}
\label{ex4.19}
Prove directly (without Rice's theorem) that \(K\le_1\text{Fin}\)
\end{exercise}
\begin{proof}
Let
\begin{equation*}
\varphi_{f(x)}(s)=
\begin{cases}
0&x\not\in K_s\\
\text{undefined}&x\in K_s
\end{cases}
\end{equation*}
where \(K_s=W_{e,s}\) for some \(e\) s.t. \(K=W_e\). If \(x\in K\), then
\(\dom{\varphi_{f(x)}}\) is finite
\end{proof}
\begin{exercise}
For any \(x\) show that \(\overline{K}\le_1\{y:\varphi_x=\varphi_y\}\) and
\(\overline{K}\le_1\{y:W_x=W_y\}\) 
\end{exercise}
\begin{proof}
Use the method of exercise \ref{ex4.19}. If \(x\not\in W_x\), then
\(\dom{\varphi_{f(x)}}=\omega\).
\end{proof}
\begin{exercise}
\(\text{Ext}\neq\omega\)
\end{exercise}
\begin{proof}
Use \(K\). If \(\psi(x)\) can be extended to a recursive function, then \(K\) would
be recursive.
\end{proof}

\begin{exercise}
\begin{enumerate}
\item Disjoints sets \(A\) and \(B\) are \textbf{recursively inseparable} if there is no
recursive set \(C\) s.t. \(A\subseteq C\) and \(C\cap B=\emptyset\). Show that
there exists disjoint r.e. sets which are recursively inseparable.
\item Give an alternative proof that \(\text{Ext}\neq\omega\)
\item For \(A\) and \(B\) as in part 1, prove that \(K\equiv_1 A\) and \(K\equiv_1 B\)
\end{enumerate}
\end{exercise}
\begin{proof}
\begin{enumerate}
\item Consider \(A=\{x:\varphi_x(x)=0\}\) and \(B=\{x:\varphi_x(x)=1\}\). If there
is a such recursive set \(C\) and its characteristic function is
\(\varphi_y\), then
\begin{equation*}
\varphi_y(x)=
\begin{cases}
1&\varphi_x(x)=0\\
1&\dots\\
0&\dots\\
0&\varphi_x(x)=1\\
\end{cases}
\end{equation*}
hence \(\varphi_y(y)\) leads to a contradiction.
\item corollary from 1.
\item The method are the same as \ref{thm1}
\end{enumerate}
\end{proof}

\begin{exercise}
A set \(A\) is \textbf{cylinder} if \((\forall B)[B\le_m A\Longrightarrow B\le_1 A]\)
\begin{enumerate}
\item Show that any index set is a cylinder
\item Show that any set of the form \(A\times\omega\) is a cylinder
\item Show that \(A\) is a cylinder iff \(A\equiv_1 B\times\omega\) for some set \(B\)
\end{enumerate}
\end{exercise}

\begin{proof}
\begin{enumerate}
\item If different \(x,y\in B\) and \(f(x)=f(y)\), we could just add redundent
computation and \(\varphi_{f(x)}=\varphi_{f(y)}\)
\item to make sure images are different by \(\omega\)
\item 
\end{enumerate}
\end{proof}

\begin{exercise}
Show that the partial recursive functions are not closed under \(\mu\), i.e.,
there is a p.r. function \(\psi\) s.t. \(\lambda x[\mu y[\psi(x,y)=0]]\) is not p.r.
\end{exercise}
\begin{proof}
\(\psi(x,y)=0\) if \(y=1\) or \(y=0\) and \(\varphi_x(x)\downarrow\).
\end{proof}
\begin{exercise}
If \(A\) is recursive and \(B,\overline{B}\) are each \(\neq\emptyset\), then
\(A\le_m B\)
\end{exercise}
\begin{proof}
choose elements \(b\in B\) and \(b'\in\overline{B}\). Then
\begin{equation*}
\psi_{f(x)}(s)=
\begin{cases}
b&x\in A\\
b'&x\not\in A\\
\end{cases}
\end{equation*}
\end{proof}
\begin{exercise}
Prove that \(\text{Inf}\equiv_1\text{Tot}\equiv_1\text{Con}\)
\end{exercise}
\begin{proof}
\(\text{Tot}\equiv_1\text{Con}\) is obvious. For \(\text{Inf}\le_1\text{Con}\),
define
\begin{equation*}
\psi(e,x)=
\begin{cases}
0&\text{if }(\exists y>x)[\varphi_e(y)\downarrow]\\
\uparrow&\text{otherwise}
\end{cases}
\end{equation*}
\end{proof}

\begin{exercise}
\(\text{Fin}\le_1\text{Cof}\)
\end{exercise}
\begin{proof}
\begin{equation*}
\varphi_{f(e)}(s)=
\begin{cases}
\uparrow&\text{if } W_{e,s+1}-W_{e,s}\neq\emptyset\\
0&\text{otherwise}
\end{cases}
\end{equation*}
\end{proof}
\subsection{Recursive Permutation and Myhill's Isomorphism Theorem}
\label{sec:org72462dd}
\begin{definition}[]
\begin{enumerate}
\item A \textbf{recursive permutation} is a 1:1, recursive function from \(\omega\) to \(\omega\)
\item A property of set is \textbf{recursively invariant} if it's invariant under all
recursive permutation
\end{enumerate}
\end{definition}
Examples:
\begin{enumerate}
\item \(A\) is r.e.
\item \(A\) has cardinality n
\item \(A\) is recursive
\end{enumerate}


Properties that not recursively invariant:
\begin{enumerate}
\item \(2\in A\)
\item \(A\) contains the even integers
\item \(A\) is an index set
\end{enumerate}


\begin{definition}[]
A is \textbf{recursively isomorphic} to \(B\) (written \(A\equiv B\)) if there is a
recursive permutation \(p\) s.t. \(p(A)=B\)
\end{definition}

\begin{definition}[]
The equivalence classes under \(\equiv\) are called \textbf{recursive isomorphism types}
\end{definition}

\begin{theorem}[Myhill Isomorphism Theorem]
\(A\equiv B\Longleftrightarrow A\equiv_1 B\)
\end{theorem}
\begin{proof}
(\(\Longrightarrow\)) trivial.

(\(\Longleftarrow\)) Let \(A\le_1 B\) via \(f\) and \(B\le_1\) via \(g\). We define a
recursive permutation \(h\) by stages so that \(h(A)=B\). We let
\(h=\bigcup_sh_s\), where \(h_0=\emptyset\) and \(h_s\) is that portion of \(h\)
defined by the end of stage \(s\). Assume \(h_s\) is given so that in particular
we can effectively check for membership in \(\dom{h_s}\) and \(\ran{h_s}\) which
we both assume finite

\emph{Stage} \(s+1=2x+1\). Assume that \(h_s\) is \(1:1\), \(\dom{h_s}\) is finite and \(y\in
   A\) iff \(h_s(y)\in B\) for all \(y\in\dom{h_s}\).If \(h_s(x)\) is defined, do
nothing. Otherwise enumerate the set
\(\{f(x),f(h_s^{-1}f(x)),\dots,f(h_s^{-1}f)^n(x),\dots\}\) until the fist
element \(y\) not yet in \(\ran{h_s}\). Define \(h_{s+1}(x)=y\). \(y\) must exist
since \(f\) and \(h_s\) are \(1:1\) and \(x\not\in\dom{h_s}\)

\emph{Stage} \(s+1=2x+2\). Define \(h^{-1}(x)\) similarly with \(f,h_s,\dom{}\) and
\(\ran{}\) replaced by \(g,h_s^{-1},\ran{},\dom{}\) respectively
\end{proof}

\begin{definition}[]
A function \(f\) \textbf{dominates} a function \(g\) if \(f(x)\ge g(x)\) for almost every
(all but finitely many) \(x\in\omega\)
\end{definition}

\begin{exercise}[$\times$]
Prove that the primitive recursive permutations do not form a group under composition
\end{exercise}
\begin{proof}
Define \(g(x)=\mu yT(e,x,y)\). \(g\) dominates all primitive recursive functions
since \(y\ge U(y)\) for all \(y\). Suppose \(f\) is a primitive recursive
permutation and \(f(g(x))=x\) if \(x\) is even. Note that given \(y\) we can
primitively recursively compute whether there is an \(x\) s.t. \(g(x)=y\)
\end{proof}
\section{Fundamentals of Recursively Enumerable Sets and the Recursion Theorem}
\label{sec:org129927f}
\subsection{Equivalent Definitions of Recursively Enumerable Sets}
\label{sec:orgaa28ca0}
\end{document}